package org.example.leetCode;

import org.example.entity.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 145. 二叉树的后序遍历
 * 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
 */
public class Code145 {
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        dfs(list,root);
        return list;
    }

    private void dfs(ArrayList<Integer> list, TreeNode root) {
        if(root==null)return;
        dfs(list,root.left);
        dfs(list,root.right);
        list.add(root.val);
    }

    public List<Integer> d(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();

        if (root == null) return list;

        TreeNode[] stack=new TreeNode[100];
        int top=0;
        stack[0]=root;

        TreeNode node;
        while (top>=0){
            node=stack[top--];
            list.add(node.val);

            if(node.left!=null){
                stack[++top]=node.left;
            }
            if(node.right!=null){
                stack[++top]=node.right;
            }
        }
        Collections.reverse(list);
        return list;
    }
}
